\subsubsection{Übung iv \buchmann{8.6.7}}

\( n = 341 \) kann laut Miller-Rabin-Test keine Primzahl sein, da mit
\begin{align*}
 s &= 2\\
 d &= \frac{341 - 1}{2^2} = 85
\end{align*}
und dem Zeugen \( a = 2 \) gilt
\[
 2^{85} \equiv 32 \not\equiv 1 \mod 341
\]
und
\begin{flalign*}
 2^{2^{0} * 85} &\equiv 2^{85} \equiv 32 \not\equiv -1 \mod 341 \:\:\:(\text{zur Verdeutlichung nochmal aufgeführt})\\
 2^{2^{1} * 85} &\equiv 1 \not\equiv -1 \mod 341
\end{flalign*}

Damit sind beide Bedingungen \buchmann{p.129, (8.2) und (8.3)} nicht erfüllt, \(a = 2\) ist Zeuge, dass 341 nicht prim ist.